#define _CRT_SECURE_NO_WARNINGS
#include"sort.h"

void swap(int& a, int& b)
{
	int temp = a;
	a = b;
	b = temp;
}

array<int, 10>::iterator partition(array<int, 10>& arr, array<int, 10>::iterator begin, array<int, 10>::iterator end)
{
	int pivot = *end;
    auto i = begin ;
	for (auto j = begin; j < end; j++)
	{
		if (*j <= pivot)
		{
			iter_swap(i, j);
			i++;
		}
	}
	iter_swap(i, end);
	return i;
}

void quick_sort(array<int, 10>&arr, array<int, 10>::iterator begin, array<int, 10>::iterator end)
{
	if (begin < end)
	{
		auto temp = partition(arr, begin, end);
		quick_sort(arr, begin, temp - 1);
		quick_sort(arr, temp + 1, end);
	}
}

void quick_sort_non_recursion(array<int, 10>& arr, array<int, 10>::iterator begin, array<int, 10>::iterator end)
{
	stack<array<int,10>::iterator>st;
	st.push(end);
	st.push(begin);
	while (!st.empty())
	{
		auto left = st.top();
		st.pop();//attention:put once and take once.
		auto right = st.top();
		st.pop();
		auto temp = partition(arr, left, right);
		if (temp - 1 > left)
		{
			st.push(temp - 1);
			st.push(left);
		}
		if (right > temp + 1)
		{
			st.push(right);
			st.push(temp + 1);
		}
	}
}
